package com.ctwom.algorithm.questions.Acalculate;

/**
 *  等价多米诺骨牌对的数量
 *  思路：创建二维数组【先行后列】存入用例，然后两数中更大的作为十位数值，较小的作为个位数值，
 *  因为两个数所以我们的算法得到的数值为1～99创建一个长度为100的数组，把乘完后的两位数放到对应的两位数数组槽内并把槽内值+1
 *  然后记录这些槽-1的值即可了（可以在遍历时先计算再+1避免再次循环）
 */
public class NumEquivDominoPairs {

    public static void main(String[] args) {
        int[][] dominoes = {{1,2},{2,1},{3,4},{5,6},{1,2},{5,6},{5,6},{5,6},{5,6}};
        System.out.println(numEquivDominoPairs(dominoes));
    }

    /**
     * 给你一个由一些多米诺骨牌组成的列表 dominoes。
     * 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
     * 形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
     * 在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
     *
     * 示例：
     * 输入：dominoes = [[1,2],[2,1],[3,4],[5,6],[1,2],[5,6],[5,6],[5,6],[5,6]]
     * 输出：(0+1+2) + (0+1+2+3+4) = 13
     *
     * @param dominoes
     * @return
     */
    public static int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;//返回结果
        int[] arr = new int[100];//由于整数还二维数组，所以最多99，所以创建长度为100的数组，用于统计每个一维数组的数量
        for (int i = 0; i < dominoes.length; i++) {
            // 整体就是通过比较一维数组的0位和1位数值大的作为十位小的作为个位，求出两位数，存入arr数组中
            // 一个不算匹配上，只有出现下一个才算匹配一次；
            // 之后再出现第N个相当于和之前的N-1个都匹配，也就是每来一个新的匹配的N，就相当于增加了N-1对
            // 所以就是 0+1+2+3+4+5+。。。N-1
            int index = dominoes[i][0] > dominoes[i][1] ? dominoes[i][0]*10+dominoes[i][1] : dominoes[i][1]*10+dominoes[i][0];
            //这里主要解决的是result加的是N-1，而arr[index]是为了下一次result计算使用
            result = arr[index] + result;
            arr[index]++;
        }
        return result;
    }
}
